/**
 * 二叉树-最小深度（深度优先，后序遍历（左右中），递归）-力扣111
 */
public class Practice_27 {
    public static void main(String[] args) {

        TreeNode head = new TreeNode(1);

        //    head.left = new TreeNode(2);

        head.right = new TreeNode(3);

        //  head.left.left = new TreeNode(4);

        // head.left.right = new TreeNode(5);

        //  head.right.left = new TreeNode(6);

        head.right.right = new TreeNode(7);


        int height = minDepth(head);



    }

    public static int minDepth(TreeNode root) {


        return getHeight(root);

    }

    //求最小深度，使用算最大深度的方法：后序遍历（左右中）
    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }//先判断空，为空返回0

        int leftHeight = getHeight(root.left);//左侧遍历
        int rightHeight = getHeight(root.right);//右侧遍历

        //左子树为空，取右子树
        if (root.left == null && root.right != null) {
            return 1 + rightHeight;
        }
        //右子树为空，取左子树
        if (root.right == null && root.left != null) {
            return 1 + leftHeight;
        }
        return leftHeight >= rightHeight ? 1 + rightHeight : 1 + leftHeight;//左右子树都不为空，取最小值+1

    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
